1817C - Similar Polynomials - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define int ll
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define SZ(a) (int(a.size()))

typedef long long ll;
typedef double db;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
#define debug(...) fprintf(stderr, __VA_ARGS__)
std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }

constexpr int N = 2500100, P = 1e9 + 7;

int d, fac[N], inv[N], a[N], b[N];
int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % P;
        a = a * a % P, b >>= 1;
    }
    return res;
}
int C(int n, int m) {
    if(n < 0 || m < 0 || n < m) return 0;
    return fac[n] * inv[m] % P * inv[n - m] % P;
}
int f(int arr[], int k, int x) {
    int res = 0;
    for(int i = 0; i <= k; i++) {
        int coef = ((k - i) % 2 ? P - 1 : 1ll) * C(k, i) % P * arr[x + i] % P;
        res = (res + coef) % P;
    }
    return res;
}
signed main() {
    scanf("%lld", &d);
    for(int i = 0; i <= d; i++) scanf("%lld", &a[i]);
    for(int i = 0; i <= d; i++) scanf("%lld", &b[i]);
    fac[0] = 1;
    for(int i = 1; i <= d; i++) fac[i] = fac[i - 1] * i % P;
    inv[d] = qpow(fac[d], P - 2);
    for(int i = d; i; i--) inv[i - 1] = inv[i] * i % P;
    int a0 = f(a, d - 1, 0), a1 = f(a, d - 1, 1);
    int b0 = f(b, d - 1, 0);
    printf("%lld\n", (b0 - a0 + P) * qpow(a1 + P - a0, P - 2) % P);
    debug("time=%.4lfs\n", (db)clock()/CLOCKS_PER_SEC);
    return 0;
}